class Solution:
    def maxProfit(self, k: int, prices: list) -> int:
        if len(prices) <= 1:
            return 0
        if k >= len(prices) / 2:
            return self.maxProfit_tanxin(prices)
        bug_list = [-prices[0] for i in range(k + 1)]
        sell_list = [0 for i in range(k + 1)]
        for now_price in prices:
            for i in range(1, k + 1):
                bug_list[i] = max(bug_list[i], sell_list[i - 1] - now_price)
                sell_list[i] = max(sell_list[i], bug_list[i] + now_price)
        return sell_list[-1]

    def maxProfit_tanxin(self, prices: list) -> int:
        res = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                res += (prices[i] - prices[i - 1])
        return res


a = Solution()
print(a.maxProfit(2, [2, 4, 1]))  # 2
print(a.maxProfit(2, [3, 2, 6, 5, 0, 3]))  # 7
print(a.maxProfit(5, [3, 2, 6, 5, 0, 3]))  # 7
